//扩展kmp
public class Solution2223 {
    public long sumScores(String s) {
        int[] z=new int[s.length()];
        for (int i=1,l=0,r=0;i<s.length();i++){
            if (i<=r && z[i-l]<r-i+1){
                z[i]=z[i-l];
            }else {
                z[i]=Math.max(0,r-i+1);
                while (i+z[i]<s.length() && s.charAt(z[i])==s.charAt(i+z[i])){
                    z[i]++;
                }
            }
            if (i+z[i]-1>r){
                l=i;
                r=i+z[i]-1;
            }
        }
        long sum=0;
        for (int j : z) {
            sum += j;
        }
        return sum+s.length();
    }

    public static void main(String[] args) {
        System.out.println(new Solution2223().sumScores("babab"));
    }
}
